#pragma once
#include <iostream>
#include <vector>
#include <queue>
#include <memory>
using namespace std;
template<class T>
struct TreeNode
{
    TreeNode(T val) 
        :_val(val)
        ,_left(nullptr)
        ,_right(nullptr)
    {}
    ~TreeNode()
    {}
    T _val;
    shared_ptr<struct TreeNode<T>> _left;
    shared_ptr<struct TreeNode<T>> _right;
};
template<class T>
class Tree
{
    typedef struct TreeNode<T> Node;
public:
    Tree(T val=0)
        :_root(new Node(val))
    {}
    bool insert(T val)
    {
        shared_ptr<Node> node(new Node(val));
        queue<shared_ptr<Node>> q;
        q.push(_root);
        while(!q.empty())
        {
            size_t sz = q.size();
            while(sz--)
            {
                shared_ptr<Node> tmp = q.front();
                q.pop();
                if(!tmp->_left)
                {
                    tmp->_left = node;
                    return true;
                }
                else q.push(tmp->_left);
                if(!tmp->_right)
                {
                    tmp->_right = node;
                    return true;
                }
                else q.push(tmp->_right);
            }
        }
        return false;
    }
    void Debug()
    {
        queue<shared_ptr<Node>> q;
        q.push(_root);
        while(!q.empty())
        {
            size_t sz = q.size();
            while(sz--)
            {
                shared_ptr<Node> tmp = q.front();
                q.pop();
                cout<<tmp->_val<<' ';
                if(tmp->_left) q.push(tmp->_left);
                if(tmp->_right) q.push(tmp->_right);
            }
            cout<<endl;
        }
    }
    ~Tree()
    {}
private:
    shared_ptr<Node> _root;
};